#include "nemu.h"

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <sys/types.h>
#include <regex.h>
#include <stdlib.h>
enum {
	NOTYPE = 256, EQ = 257, NUM = 258

	/* TODO: Add more token types */

};

static struct rule {
	char *regex;
	int token_type;
} rules[] = {

	/* TODO: Add more rules.
	 * Pay attention to the precedence level of different rules.
	 */

	{" +",	NOTYPE},				// spaces
	{"\\+", '+'},					// plus
	{"==", EQ},						// equal
	{"\\-",'-'},
	{"\\*",'*'},
	{"\\/",'/'},
	{"\\(",'('},
	{"\\)",')'},
	{"[0-9]+",NUM}
};

#define NR_REGEX (sizeof(rules) / sizeof(rules[0]) )

static regex_t re[NR_REGEX];

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
	int i;
	char error_msg[128];
	int ret;

	for(i = 0; i < NR_REGEX; i ++) {
		ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
		if(ret != 0) {
			regerror(ret, &re[i], error_msg, 128);
			Assert(ret == 0, "regex compilation failed: %s\n%s", error_msg, rules[i].regex);
		}
	}
}

typedef struct token {
	int type;
	char str[32];
} Token;

Token tokens[32];
int nr_token;

static bool make_token(char *e) {
	int position = 0;
	int i;
	regmatch_t pmatch;
	
	nr_token = 0;

	while(e[position] != '\0') {
		/* Try all rules one by one. */
		for(i = 0; i < NR_REGEX; i ++) {
			if(regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
				char *substr_start = e + position;
				int substr_len = pmatch.rm_eo;
				//Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s", i, rules[i].regex, position, substr_len, substr_len, substr_start);
				position += substr_len;
				if(rules[i].token_type == NOTYPE) {
					break;
				}
				/* TODO: Now a new token is recognized with rules[i]. Add codes
				 * to record the token in the array `tokens'. For certain types
				 * of tokens, some extra actions should be performed.
				 */
				switch(rules[i].token_type) {
					case NUM:
						tokens[nr_token].type = NUM;
						strncpy(tokens[nr_token].str, substr_start, substr_len);
						tokens[nr_token].str[substr_len] = '\0'; 
						nr_token++;
						break;
					case '+':
						tokens[nr_token].type = '+';
						nr_token++;
						break;
					case '-':
						tokens[nr_token].type = '-';
						nr_token++;
						break;
					case '*':
						tokens[nr_token].type = '*';
						nr_token++;
						break;
					case '/':
						tokens[nr_token].type = '/';
						nr_token++;
						break;
					case '(':
						tokens[nr_token].type = '(';
						nr_token++;
						break;
					case ')':
						tokens[nr_token].type = ')';
						nr_token++;
						break;
					default: panic("please implement me");
				}

				break;
			}
		}

		if(i == NR_REGEX) {
			printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
			return false;
		}
	}

	return true; 
}
bool check_parenthness(uint32_t lp,uint32_t rp){
	int st=0;
	if(tokens[lp].type == '(' && tokens[rp].type == ')'){
		uint32_t i=1;
		for(;lp+i<rp;i++){
			if(tokens[lp+i].type=='(')st++;
			if(tokens[lp+i].type==')')st--;
			if(st<0)return false;
		}
		if(st==0)return true;
	}
	return false;
}
int find_op(uint32_t p,uint32_t q){
	int op=-1;
	int min_pri=666;
	int parenth_depth=0;
	int i;
	for(i=p;i<=q;i++){
		if(tokens[i].type=='(')parenth_depth++;
		else if(tokens[i].type==')')parenth_depth--;
		else if(parenth_depth==0){
			if(tokens[i].type=='+'||tokens[i].type=='-'||tokens[i].type=='*'||tokens[i].type=='/'){
				int pri=tokens[i].type=='+'||tokens[i].type=='-'?1:2;
				if(pri<=min_pri){
					min_pri=pri;
					op=i;
				}
			}
		}
	}
	return op;
}
uint32_t eval(uint32_t p,uint32_t q){
	if(p > q) {
		assert(0);
	}
	else if (p == q) {
		if(tokens[p].type == NUM){
			uint32_t num = (uint32_t)strtoul(tokens[p].str,NULL,0);
			return num;
		}
		else {
			assert(0);
		}
	}
	else if (check_parenthness(p,q)==true){
		return eval(p+1,q-1);
	}
	else {
		int op=find_op(p,q);
		assert(op!=-1);
		uint32_t val1=eval(p,op-1);
		uint32_t val2=eval(op+1,q);
		switch(tokens[op].type){
			case '+': return val1+val2;
			case '-': return val1-val2;
			case '*': return val1*val2;
			case '/': 
				assert(val2 != 0);
				return val1 / val2;
			default:assert(0);
		}
	}
}
uint32_t expr(char *e, bool *success) {
	if(!make_token(e)) {
		*success = false;
		return 0;
	}
	/* TODO: Insert codes to evaluate the expression. */
	*success = true;
	return eval(0, nr_token-1);
	panic("please implement me");
	return 0;
}

